1. Field of the Invention
The present invention relates to a method, system, and program using multiple data structures to manage data in cache.
2. Description of the Related Art
A cache management system stores data maintained in storage device in a faster access media, such as a memory device, so that requests for the data from the storage can be serviced faster from the faster access cache memory. A cache management system may maintain a linked list having one entry for each data unit staged into cache from the storage. In the commonly used Least Recently Used (LRU) cache technique, if data in the cache is accessed, i.e., a cache “hit”, then the entry in the LRU list for the accessed data is moved to a Most Recently Used (MRU) end of the list. If the requested data is not in the cache, i.e., a cache miss, then the data in the cache whose entry is at the LRU end of the list may be removed (or destaged back to storage) and an entry for the new data staged into cache is added to the MRU end of the LRU list. With this LRU cache technique, data that is more frequently accessed is likely to remain in cache, while data less frequently accessed will more likely be removed from the LRU end of the list to make room in cache for newly accessed data.
In an asynchronous computing environment where multiple threads or different processors in a multi-processor environment are accessing data from the same cache, the MRU entry is protected by a lock to serialize access to the MRU entry. This means that one or more threads must wait for the thread holding the lock on the MRU entry to complete their cache hit or miss operation. In multi-threaded environments there is a significant amount of contention for this lock because all cache hits and cache misses require access to this lock. Such contention is considered undesirable for high performance and high throughput environments such as virtual memory, databases, file systems, and storage controllers.
FIG. 1 illustrates a clock data structure (or “clock”) 2 known in the prior art to manage data cached from a storage device. The clock 2 comprises a circular buffer. The clock includes a clock hand 4 that points between a head entry 6 and tail entry 8 of the clock 2. Data from storage is added to the head entry 6. The clock algorithm maintains a “page reference bit” for each clock 2 entry, or page. When data is first brought into the cache from storage, the page reference bit for the entry for that cached data is set to zero. When data in cache is accessed, the page reference bit for the accessed data is set to one.
To replace data in cache with newly accessed data from storage, if the head entry 8 at the clock hand 4 has a page reference bit of zero, then the data corresponding to the head entry 8 is destaged from cache, and information on the new page is added to the head entry 6. If the page reference bit for the current head entry 8 is one, then that page reference bit is reset to zero and the clock hand 4 moves forward through the clock 2 until finding a head entry 8 having a page reference bit of zero to replace. In virtual memory applications, the page reference bit can be changed by the hardware.
One advantage of the clock cache technique is that there is no need to move a page to an MRU position for a cache hit such as the case with the LRU cache technique, which requires a lock and serialization to move the entry in the LRU list for accessed data to the MRU position. Furthermore, the hit ratio of the clock cache technique is usually comparable to that of the LRU cache method. For this reason, variants of the clock cache technique are used in many operating systems and application programs. However, a lock is still required for a cache miss when adding a page to the head entry 8 of the clock structure. Thus, both the LRU and clock cache techniques require lock contention when replacing data in cache.
For these reasons, there is a need in the art to provide techniques for managing data in a cache.